# -*- coding: utf-8 -*-

# 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案
# 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1
# 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2)

# # 最笨的方法 竟然通过了...
# class Solution(object):
#     def threeSumClosest(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: int
#         """
#         if len(nums) < 3:
#             return None;
#         rtn = nums[0] + nums[1] + nums[2];
#         for i in xrange(0, len(nums) - 2):
#             for j in xrange(i + 1, len(nums) - 1):
#                 for k in xrange(j + 1, len(nums)):
#                     if abs(nums[i] + nums[j] + nums[k] - target) < abs(rtn - target):
#                         rtn = nums[i] + nums[j] + nums[k];
#                     if rtn==target:
#                         return rtn;
#         return rtn;

# n平方量级的解法
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort();
        rtn = nums[0] + nums[1] + nums[2];
        for i in xrange(0, len(nums) - 2):
            begin_index = i + 1;
            end_index = len(nums) - 1;
            while begin_index < end_index:
                sum3 = nums[i] + nums[begin_index] + nums[end_index];
                if sum3 < target:
                    begin_index += 1;
                else:
                    end_index -= 1;
                if abs(sum3 - target) < abs(rtn - target):
                    rtn = sum3;
                if (rtn==target):
                    return rtn;
        return rtn;

t = Solution();
print t.threeSumClosest([-1,2,1,-4,6], 8);